1446B - Catching Cheaters - CodeForces Solution

#include<bits/stdc++.h>
//DP10170015
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define endl '\n'
template<class T>
void print(const vector<T> &v){
       for(T i = 0;i<(ll)(v.size());i++){
       cout<<v[i]<<" ";
       }
}
template<class T>
void input(vector<T> &v){
       for(T i = 0;i<(ll)(v.size());i++){
       cin>>v[i];
       }
}

vector<ll> v10(200001);
vector<ll> seg(1000000);
void build(ll ind,ll low,ll high){
if(low==high){
seg[ind] = v10[low];
return;
}
ll mid = (low+high)/2;
build((2*ind)+1,low,mid);
build((2*ind)+2,mid+1,high);
seg[ind] = max(seg[(2*ind)+1],seg[(2*ind)+2]);
}
ll query(ll ind,ll low,ll high,ll l,ll r){
if(low>=l&&high<=r){
return seg[ind];
}
if(high<l||low>r){
return INT_MIN;
}
ll mid = (low+high)/2;
ll left = query((2*ind)+1,low,mid,l,r);
ll right = query((2*ind)+2,mid+1,high,l,r);
return max(left,right);
}

const ll N = 1e6;
vector<bool> sv(N + 1, true);
void sieve() {
    sv[0] = sv[1] = false;
    for(int i = 2; i * i <= N; i++) {
        if(sv[i]) {
            for(int j = i * i; j <= N; j += i) {
                sv[j] = false;
            }
        }
    }
}

ll mpow(ll a, ll n, ll m)
{
    ll res = 1;
    while (n)
    {
        if (n & 1)
        {
            res = ((res % m) * (a % m)) % m;
            n--;
        }
        else
        {
            a = ((a % m) * (a % m)) % m;
            n /= 2;
        }
    }
    
    return res % m;
}
 
void solve(){
       ll n,m;
       cin>>n>>m;
       string s1,s2;
       cin>>s1>>s2;
       ll dp[n+1][m+1];
       ll ans = INT_MIN;
       memset(dp,0,sizeof(dp));
       for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j] = max(dp[i][j],dp[i-1][j-1]+2);
            }
            else{
                dp[i][j] = max({dp[i][j],dp[i][j-1]-1,dp[i-1][j]-1});
            }
            ans = max(ans,dp[i][j]);
        }
       }
       cout<<ans<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
       int t = 1;
       //cin>>t;
       while(t--){
              solve();
       }
       return 0;
}